package nsum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.cn/problems/3sum/
 */
public class _15_三数之和 {

    public static void main(String[] args) {
        int[] nums = new int[]{-1,0,1,2,-1,-4};
        _15_三数之和 _15_三数之和 = new _15_三数之和();
        List<List<Integer>> results = _15_三数之和.threeSum(nums);
        System.out.println(results);
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int a = nums[i];

            int lo = i + 1;
            int ro = nums.length -1;

            int target = 0 - a;

            while (lo < ro) {
                int b = nums[lo];
                int c = nums[ro];

                if (b + c > target) {
                    ro--;
                } else if (b + c < target) {
                    lo++;
                } else if (b + c == target) {
                    List<Integer> result = new ArrayList<>();
                    result.add(nums[i]);
                    result.add(nums[lo]);
                    result.add(nums[ro]);
                    resultList.add(result);
                    lo++;
                    ro--;

                    // 去重复
                    while (lo < ro && nums[lo] == nums[lo-1]) lo++;
                    while (lo < ro && nums[ro] == nums[ro+1]) ro--;

                }
            }

        }
        return resultList;
    }
}
